3107. Odd Numbers of Divisors

Given a positive odd integer k and two positive integers low and high, determine how many integers between low and high contain exactly k divisors.

Input. The first line of the input contains a positive integer c (0 < c < 100,000), the number of test cases to follow. Each case consists of a line containing three integers: k, low, and high (1 < k < 10000, 0 < low ≤ high < 10¹⁰). k will always be an odd integer.

Output. Output for each case consists of one line: the number of integers between low and high, inclusive, that contain exactly k divisors.

Sample Input	Sample Output
3 3 2 49 9 1 100 5 55 235	4 2 1

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

В задаче требуется узнать, сколько чисел из интервала [low; high] имеют в точности k делителей. Число содержит нечетное количество делителей (k по условию задачи нечетно), только если оно является полным квадратом.

Построим отображение (map) m таким образом, чтобы m[i] содержало в отсортированном виде массив чисел, у каждого из которых в точности i делителей. Например

m[3] = (4, 9, 25, 49, 121, 169, 289, 361, 529, … )

m[5] = (16, 81, 625, …)

m[7] = (64, …)

Тогда ответ на задачу можно найти при помощи бинарного поиска на интервале [low; high] в массиве m[k].

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <cmath>

#include <map>

#include <algorithm>

using namespace std;

map<int, vector<long long> > m;

long long tests, low, high, res;

int k;

int CountDiv2(long long n)

{

int c, i, res = 1;

for(i = 2; i <= sqrt(1.0*n); i++)

{

if (n % i == 0)

{

c = 0;

while(n % i == 0) n /= i, c++;

res *= (2 * c + 1);

}

}

if (n > 1) res *= 3;

return res;

}

int main(void)

{

for (long long i = 2; i < sqrt(1.0*10000000000LL); i++)

m[CountDiv2(i)].push_back(i*i);

scanf("%d",&tests);

while(tests--)

{

scanf("%d %lld %lld",&k,&low,&high);

res = upper_bound(m[k].begin(),m[k].end(),high) –

lower_bound(m[k].begin(),m[k].end(),low);

printf("%lld\n",res);

}

}